<!DOCTYPE html>
<html lang="en">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/apple-touch-icon.png">
  <link rel="icon" type="image/png" href="https://img.fungnotl.cn/basket.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  <meta name="description" content="">
  <meta name="author" content="John Doe">
  <meta name="keywords" content="">
  <title>桶排序之计数排序与基数排序 ~ fungnotl的博客</title>

  <link rel="stylesheet" href="/lib/font-awesome/css/all.min.css"  >
<link rel="stylesheet" href="/lib/bootstrap/css/bootstrap.min.css"  >
<link rel="stylesheet" href="/lib/mdbootstrap/css/mdb.min.css"  >
<link rel="stylesheet" href="/lib/github-markdown/github-markdown.min.css"  >
<link rel="stylesheet" href="//at.alicdn.com/t/font_1067060_qzomjdt8bmp.css">


  <link rel="stylesheet" href="/lib/prettify/tomorrow-night-eighties.min.css"  >

<link rel="stylesheet" href="/css/main.css"  >


  <link rel="stylesheet" href="/lib/fancybox/jquery.fancybox.min.css"  >


</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>fungnotl的博客</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/">主页</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/archives/">归档</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/tags/">标签</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/about/">我</a>
          </li>
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>


</nav>

    <div class="view intro-2" id="background"
         style="background: url('https://fungnotl-img.oss-cn-hangzhou.aliyuncs.com/index.jpg')no-repeat center center;
           background-size: cover;
           background-attachment: fixed;">
      <div class="full-bg-img">
        <div class="mask rgba-black-light flex-center">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              <br>
              
                <p class="mt-3">
                  <i class="fas fa-calendar-alt" aria-hidden="true"></i>&nbsp;
                  Monday, January 27th 2020, 4:00 am
                </p>
              

              <p>
                
                  
                  &nbsp;<i class="far fa-chart-bar"></i>
                  <span class="post-count">
                    582 字
                  </span>&nbsp;
                

                
                  
                  &nbsp;<i class="far fa-clock"></i>
                  <span class="post-count">
                      2 分钟
                  </span>&nbsp;
                

                
                  <!-- 不蒜子统计文章PV -->
                  
                  &nbsp;<i class="far fa-eye" aria-hidden="true"></i>&nbsp;
                  <span id="busuanzi_container_page_pv">
                    <span id="busuanzi_value_page_pv"></span> 次
                  </span>&nbsp;
                
              </p>
            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="py-5 z-depth-3" id="board">
        <div class="post-content mx-auto" id="post">
          <div class="markdown-body">
            <h1 id="桶排序之计数排序和基数排序"><a href="#桶排序之计数排序和基数排序" class="headerlink" title="桶排序之计数排序和基数排序"></a>桶排序之计数排序和基数排序</h1><h3 id="桶排序"><a href="#桶排序" class="headerlink" title="桶排序"></a>桶排序</h3><blockquote>
<p>一种常见的排序算法,工作原理是将数组分到有限数量的桶子里,每个桶子再个别进行排序(会使用递归的方式继续使用桶排序进行排序或者使用其他的排序算法).</p>
</blockquote>
<h3 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h3><p>计数排序是桶排序的一种特殊情况<br><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9mdW5nbm90bC1pbWcub3NzLWNuLWhhbmd6aG91LmFsaXl1bmNzLmNvbS8lRTYlQTElQjYlRTYlOEUlOTIlRTUlQkElOEYvQ291bnRTb3J0LmdpZg" srcset="/img/loading.gif" alt="计数排序"></p>
<ul>
<li>从图中可以看出,待排序数字在[1,9]范围内;</li>
<li>创建9个空桶,将待排序数字分别放在对应的桶中;</li>
<li>再依次将桶中的元素按照桶的顺序拿出;</li>
</ul>
<p>代码实现:</p>
<pre><code class="java">public class CountSort {
    public static void main(String[] args) {
        int[] arr = {2, 4, 2, 3, 7, 1, 1, 1, 0, 5, 6, 9, 8, 7, 4, 0, 9};
        int[] result = sort(arr);
        System.out.println(Arrays.toString(result));
    }
    static int[] sort(int[] arr){
        //新建一个数组用来存放最终的结果
        int[] result = new int[arr.length];
        //10个桶
        int[] count = new int[10];
        //计数,计算每个桶中有多少个数字
        for (int i = 0; i &lt; arr.length; i++) {
            count[arr[i]]++;
        }

        System.out.println(Arrays.toString(count));
        //累加数组,得到该桶的最后一个数字在最终数组中排在第几位的数字
        for (int i = 1; i &lt; count.length; i++) {
            count[i] = count[i] + count[i-1];
        }
        System.out.println(Arrays.toString(count));
        //倒序迭代,将待排数字拿出放入累加数组中,得到结果数组中的位置,放入(建议拿出笔来算算)
        for (int i = arr.length-1; i &gt;= 0; i--) {
            result[--count[arr[i]]] = arr[i];
        }
        return result;
    }
}</code></pre>
<h3 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h3><p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9mdW5nbm90bC1pbWcub3NzLWNuLWhhbmd6aG91LmFsaXl1bmNzLmNvbS8lRTYlQTElQjYlRTYlOEUlOTIlRTUlQkElOEYvUmFkaXhTb3J0LmdpZg" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<ul>
<li>算法思想:多关键字排序;</li>
<li>同样,将待排数字依据该数字的个位,十位.百位,千位分别放入桶中;</li>
</ul>
<p>代码实现:</p>
<pre><code class="java">public class RadixSort {

    public static void main(String[] args) {

        int[] arr = {421, 240, 225, 532, 305, 430, 124};

        int[] result = sort(arr);

        System.out.println(Arrays.toString(result));
    }

    public static int[] sort(int[] arr){
        int[] result = new int[arr.length];
        int[] count = new int[10];

        for (int i = 0; i &lt; 3; i++) {
            int division = (int) Math.pow(10, i);
            System.out.println(division);
            //得到余数
            for (int j = 0; j &lt; arr.length; j++) {
                int num = arr[j]/division % 10;

                System.out.print(num + &quot; &quot;);

                count[num]++;
            }
            System.out.println();
            System.out.println(Arrays.toString(count));

            for (int m = 1; m &lt; count.length; m++) {
                count[m] = count[m] + count[m-1];
            }

            System.out.println(Arrays.toString(count));

            for (int n = arr.length-1; n &gt;= 0; n--) {
                int num = arr[n]/division % 10;
                result[--count[num]] = arr[n];
            }
            System.arraycopy(result, 0, arr, 0, arr.length);
            Arrays.fill(count, 0);
        }
        return result;
    }
}</code></pre>
<hr>
<h1 id="Mamba-Never-Out"><a href="#Mamba-Never-Out" class="headerlink" title="Mamba Never Out"></a>Mamba Never Out</h1><p>R.I.P Mamba<br><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9mdW5nbm90bC1pbWcub3NzLWNuLWhhbmd6aG91LmFsaXl1bmNzLmNvbS8lRTYlQTElQjYlRTYlOEUlOTIlRTUlQkElOEYvS29iZS5qcGc?x-oss-process=image/format,png" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>

            <hr>
          </div>
          <br>
          <div>
            <p>
            
            
              <span>
                <i class="iconfont icon-tag"></i>
                
                  <a class="hover-with-bg" href="/tags/%E6%A1%B6%E6%8E%92%E5%BA%8F">桶排序</a>
                
                  <a class="hover-with-bg" href="/tags/%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F">计数排序</a>
                
                  <a class="hover-with-bg" href="/tags/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F">基数排序</a>
                
              </span>
            
            </p>
            
              <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://zh.wikipedia.org/wiki/Wikipedia:CC_BY-SA_3.0%E5%8D%8F%E8%AE%AE%E6%96%87%E6%9C%AC" target="_blank" rel="nofollow noopener noopener">CC BY-SA 3.0协议</a> 。转载请注明出处！</p>
            
          </div>
        </div>
      </div>
    </div>
    <div class="d-none d-lg-block col-lg-2 toc-container">
      
  <div id="toc">
    <p class="h4"><i class="far fa-list-alt"></i>&nbsp;TOC</p>
    <div id="tocbot"></div>
  </div>

    </div>
  </div>
</div>

<!-- custom -->


<!-- Comments -->
<div class="col-lg-7 mx-auto nopadding-md">
  <div class="container comments mx-auto" id="comments">
    
      <br><br>
      
      
   <!-- 来必力City版安装代码 -->
<div id="lv-container" data-id="city" data-uid="MTAyMC80Nzg4My8yNDM4MA==">
	<script type="text/javascript">
   (function(d, s) {
       var j, e = d.getElementsByTagName(s)[0];

       if (typeof LivereTower === 'function') { return; }

       j = d.createElement(s);
       j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
       j.async = true;

       e.parentNode.insertBefore(j, e);
   })(document, 'script');
	</script>
<noscript> 为正常使用来必力评论功能请激活JavaScript</noscript>
</div>
<!-- City版安装代码已完成 -->
  
  
    
  </div>
</div>

    
  </main>

  
    <a class="z-depth-1" id="scroll-top-button" href="#" role="button">
      <i class="fa fa-chevron-up scroll-top-arrow" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  <footer class="mt-5">
  <div class="text-center py-3">
    <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><b>Hexo</b></a>
    <i class="iconfont icon-love"></i>
    <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"> <b>Fluid</b></a>
    <br>

    
  
    <!-- 不蒜子统计PV -->
    
    &nbsp;<span id="busuanzi_container_site_pv">总访问量 
          <span id="busuanzi_value_site_pv"></span> 次</span>&nbsp;
  
  
    <!-- 不蒜子统计UV -->
    
    &nbsp;<span id="busuanzi_container_site_uv">总访客数 
            <span id="busuanzi_value_site_uv"></span> 人</span>&nbsp;
  
  <br>



    
  <!-- 备案信息 -->
  <a href="http://beian.miit.gov.cn/" target="_blank"
     rel="nofollow noopener">浙ICP备19040843号</a>
  


  </div>
</footer>

<!-- SCRIPTS -->
<script src="/lib/jquery/jquery.min.js" ></script>
<script src="/lib/popper/popper.min.js" ></script>
<script src="/lib/bootstrap/js/bootstrap.min.js" ></script>
<script src="/lib/mdbootstrap/js/mdb.min.js" ></script>
<script src="/js/main.js" ></script>


  <script src="/js/lazyload.js" ></script>



  
    <script src="/lib/tocbot/tocbot.min.js" ></script>
  
  <script src="/js/post.js" ></script>



  <script src="/lib/smooth-scroll/smooth-scroll.min.js" ></script>



  <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>


<!-- Plugins -->


  

  

  

  

  




  <script src="/lib/prettify/prettify.min.js" ></script>
  <script>
    $(document).ready(function () {
      $('pre').addClass('prettyprint  linenums');
      prettyPrint();
    })
  </script>



  <script src="/lib/typed/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "桶排序之计数排序与基数排序&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 50,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script src="/lib/anchor/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "false",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      getSearchFile(path);
      this.onclick = null
    }
  </script>



  <script src="/lib/fancybox/jquery.fancybox.min.js" ></script>
  <script>
    $("#post img:not(.no-zoom img, img[no-zoom])").each(
      function () {
        var element = document.createElement("a");
        $(element).attr("data-fancybox", "images");
        $(element).attr("href", $(this).attr("src"));
        $(this).wrap(element);
      }
    );
  </script>





  





</body>
</html>
